#include <vector>
#include <algorithm> // for std::max

using namespace std;


class Solution {
public:
    int jump(vector<int>& nums) {
        // 边界情况：如果数组为空或只有一个元素，不需要跳跃
        if (nums.size() <= 1) {
            return 0;
        }

        int jumps = 0;                     // 记录最少跳跃次数
        int current_end = 0;               // 标记「当前跳跃区间」的边界。在这个区间内的所有位置都可以通过上一次跳跃到达。
        int farthest = 0;                  // 记录在「当前跳跃区间」内任意位置出发，所能到达的最远距离。

        // 遍历数组，注意：我们不需要遍历最后一个元素
        // 因为一旦 current_end 或 farthest 到达或超过最后一个元素的索引，我们就已经完成了任务
        for (int i = 0; i < nums.size() - 1; ++i) {
            // 1. 「探索」：在当前跳跃区间内，不断更新能到达的最远距离
            //    对于区间内的每一个位置 i，计算从 i 能跳到的最远点 (i + nums[i])
            //    farthest 始终保存着这个最大值。
            farthest = max(farthest, i + nums[i]);

            // 2. 「决策」：当遍历到「当前跳跃区间」的边界时 (i == current_end)
            //    这意味着我们已经考察完了上一次跳跃所能到达的所有位置。
            if (i == current_end) {
                // a. 我们必须进行一次新的跳跃才能继续前进。因此，跳跃次数加一。
                jumps++;

                // b. 确定新的「跳跃区间」的边界。
                //    新的边界就是我们在当前区间内探索到的最远距离 farthest。
                //    这代表着我们下一次跳跃能到达的范围。
                current_end = farthest;

                // c. 提前退出优化：
                //    如果新的区间边界已经覆盖了或超过了数组的最后一个元素，
                //    说明下一次跳跃就能到达终点，无需再继续遍历。
                if (current_end >= nums.size() - 1) {
                    break;
                }
            }
        }

        return jumps;
    }
};